#include <bits/stdc++.h>
using namespace std;
int n, k, dp[20005][2], a[20005], mx1[20005], mx2[20005];

class Convex {
private:
    vector<tuple<int, int>> q;
    double pos(tuple<int, int> y1, tuple<int, int> y2)
    {
        return (get<0>(y2) - get<0>(y1)) * 1.0 / (get<1>(y1) - get<1>(y2));
    }

public:
    void insert(tuple<int, int> now)
    {
        if (!q.empty() && get<1>(q[q.size() - 1]) == get<1>(now)) {
            if (get<0>(q[q.size() - 1]) > get<0>(now))
                q.pop_back();
            else
                return;
        }
        while (q.size() > 1 && pos(q[q.size() - 2], q[q.size() - 1]) >= pos(q[q.size() - 1], now))
            q.pop_back();
        q.push_back(now);
    }
    int query(int x)
    {
        while (q.size() > 1 && pos(q[q.size() - 2], q[q.size() - 1]) >= x)
            q.pop_back();
        return (q.empty() ? 0x3f3f3f3f : get<0>(q.back()) + x * get<1>(q.back()));
    }
};

void solve(int l, int r, int k)
{
    if (l == r)
        return;
    int mid = (l + r) / 2;
    solve(l, mid, k);
    mx1[mid] = 0;
    for (int i = mid + 1; i <= r; i++)
        mx1[i] = max(mx1[i - 1], a[i]);
    mx2[mid + 1] = 0;
    for (int i = mid; i >= l; i--)
        mx2[i] = max(mx2[i + 1], a[i]);
    Convex q1, q2;
    int p = mid;
    for (int i = mid + 1; i <= r; i++) {
        while (p >= max(l, k - 1) && mx1[i] >= mx2[p + 1]) {
            if (dp[p][(k - 1) & 1] == 0x3f3f3f3f) {
                p--;
                continue;
            }
            q1.insert({ dp[p][(k - 1) & 1], p });
            p--;
        }
        dp[i][k & 1] = min(dp[i][k & 1], q1.query(-mx1[i]) + i * mx1[i]);
    }
    p = max(l, k - 1);
    for (int i = r; i >= mid + 1; i--) {
        while (p <= mid && mx2[p + 1] >= mx1[i]) {
            if (dp[p][(k - 1) & 1] == 0x3f3f3f3f) {
                p++;
                continue;
            }
            tuple<int, int> now = { dp[p][(k - 1) & 1] - p * mx2[p + 1], mx2[p + 1] };
            q2.insert({ dp[p][(k - 1) & 1] - p * mx2[p + 1], mx2[p + 1] });
            p++;
        }
        dp[i][k & 1] = min(dp[i][k & 1], q2.query(i));
    }
    solve(mid + 1, r, k);
}

signed main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        memset(dp[i & 1], 0x3f, sizeof(dp[i & 1]));
        solve(0, n, i);
    }
    cout << dp[n][k & 1];
    return 0;
}